#include <iostream>
#include <unordered_map>

class Node
{
public:
    int val;
    Node *next;
    Node *random;

    Node(int _val)
    {
        val = _val;
        next = NULL;
        random = NULL;
    }
};

using namespace std;

class Solution
{
public:
    Node *copyRandomList(Node *head)
    {
        unordered_map<Node *, Node *> map;
        Node *ansHead = new Node(0);
        Node *last = ansHead;
        for (Node *cur = head; cur != NULL; cur = cur->next)
        {
            Node *newNode = new Node(cur->val);
            newNode->random = cur->random;
            last->next = newNode;
            last = newNode;
            map[cur] = newNode;
        }
        for (Node *cur = ansHead; cur != NULL; cur = cur->next)
        {
            if (cur->random != NULL)
            {
                cur->random = map[cur->random];
            }
        }
        return ansHead->next;
    }
};
int main()
{
    cout << "Code138" << endl;
    Solution s;
    return 0;
}